1. Field of the Invention
The present invention relates to an image forming device and method which converts each pixel of an M-level gradation image into one of N levels (M>N) through an N-level error diffusion process, and the image forming device is appropriate for use in printers, digital copiers and facsimiles.
2. Description of the Related Art
In recent years, the improvements of high-quality printers and high-speed PCs are remarkable. The output resolution of a certain model in the recent printers has become the high resolution of 1200 ×1200 dpi and the size of dots which are outputted in 1200 dpi resolution can be changed to one of three different sizes: small, middle and large.
With the high-resolution of ink jet printers, high-density ink-jet heads for discharging the ink are provided, and the precision of paper conveyance is raised. The use of high-viscosity ink prevents the spreading of the ink discharged onto the paper, and the amount of the ink discharged is controlled to vary the size of dots in order to print one of the small, middle and large dots.
In the electro-photographic process, the high-resolution printing is achieved by increasing the diameter of the laser beam exposed to the photoconductor medium and decreasing the diameter of toner particles developed on the paper.
Furthermore, the high-resolution printing is achieved by using the optical intensity modulation technique or the pulse-width modulation technique.
In the ink jet printer, an N-level intensity image is reproduced using inks with different concentrations (or intensities).
Concentration (or intensity) is divided into light ink and dark ink (the concentration of light ink is usually diluted to ⅓-⅙ of dark ink), light ink is used in the highlight portion, and dark ink is used in the middle or high-concentration portion when the image is reproduced.
The multi-level gradation representation in the shade ink of the ink-jet printing process and the multi-level gradation representation by the dot diameter modulation in the electro-photographic process are useful techniques especially for output devices which quantize each pixel of an M-level gradation image into one of N levels (2<N<M) so that a reconstructed image is formed.
When producing a reconstructed image, it is important to raise the graininess of the image. The graininess in the highlight portion is increased by using the arrangement of high-density dots needed for printing, the dot diameter modulation, and the dark and light inks.
Generally, in order to improve the graininess, a measure for making the distribution of small dots that are had to notice by the human eyes uniform has been taken.
As for the printer with no capability of performing the dot diameter modulation, the technique of the area gradation is selected which carries out the gradation representation by the area that is occupied by the number of output dots. In such a printer, the representation of the middle-concentration portion is achieved with the output dots having a uniform distribution, and the periphery of each dot is not easily visible and the graininess is good. This is the case for the printer having a high resolution.
However, in the case of the printer having a low resolution, the large dots are outputted in the highlight portion, the intervals of such dots become large, the isolated dots are conspicuous, and the graininess becomes poor. In the case of the printer having a high resolution, the dot diameter becomes small, a large number of output dots are outputted, and the graininess is improved.
In the dot diameter modulation technique, a large number of small dots are outputted to express the concentration, and the graininess is improved. If light ink is used in order to make the small dot appear mostly and to express the concentration, the graininess is further improved.
Generally, in the case where the image data of M-level gradation is outputted to the printer in which the outputting of N (M>N) levels is possible, the quantization processing which reduces the number of the gradation levels of each pixel is performed. The error diffusion process and the average error minimum method are used as the technique of such quantization processing, and they are excellent in gradation nature and image sharpness.
The error diffusion process is a pseudo halftoning technique which makes the weighting the pixel to which the circumference has not quantized yet the quantization error produced at the time of quantization of a certain pixel, and is allotted to the spread portion.
Moreover, the average error minimum method is a pseudo halftoning technique which corrects the image data value of the target pixel with the weighted mean value of the quantization errors produced in the neighboring pixels with which the quantization is already performed.
By such techniques, the quantization errors are stored for all images, and a reconstructed image becomes excellent in gradation nature. The error diffusion process and the average error minimum method are similar to each other since they differ only in the timing of performing the error diffusion. In the following description, the error diffusion process and the average error minimum method are collectively called the error diffusion process.
FIG. 1 shows the composition of a conventional image forming device which performs an error diffusion process.
In the conventional image forming device of FIG. 1, the input buffer 1, the adder 2, the quantization unit 3, the output buffer 4, the subtractor 5, the error memory 6 and the error diffusion matrix 7 are provided. The input value from the input buffer 1, and the error calculated by using the error diffusion matrix 7 are supplied to the adder 2. The resulting input value from the adder 2 is supplied to the quantization unit 3. The input value of the adder 2 supplied to the quantization unit 3, and the quantization threshold of the quantization unit 3 are compared, and the output value is determined. The output value from the quantization unit 3 is supplied to the output buffer 4. The difference between the input value supplied to the quantization unit 3 and the output value supplied to the output buffer 4 is computed by the subtractor 5, and the calculated difference is stored into the error memory 6 as an error of the target pixel.
In the processing of the following pixel, in the error diffusion matrix 7, the error of the target pixel is calculated based on the errors of the 4 neighboring pixels near the target pixel. The error of the target pixel calculated with the error diffusion matrix 7 is supplied to the adder 2, and the sum of the input value and the error is produced by the adder 2.
By repeating the above processing for every pixel, the error diffusion process is carried out so that the concentration of the image is stored.
FIG. 2 shows the ratio of output dots in the 4-level error diffusion process as an example of the multi-level error diffusion process.
Suppose that the 4-level quantization output value is set to 0 (blank dot), 85 (small dot), 170 (middle dot), and 255 (large dot), respectively. The ratio of small dots is increased when the input data level increases from 0 to 85, and the ratio of small dots becomes 100% when the input data level is 85. When the input data level is in the range of 85-170, the ratio of small dots is decreased while the ratio of middle dots is increased. The ratio of middle dots becomes 100% when the input data level is 170. When the input data level is in the range of 170-255, the ratio of middle dots is decreased while the ratio of large dots is increased. The ratio of large dots becomes 100% when the input data level is 255.
The multi-level error diffusion process is excellent in gradation nature, but the quantization output value changes greatly in response to the change of the input data level, which causes a visual level difference to be produced in such changing portions.
Here, the four-level error diffusion process, which converts 256-level gradation input data (each pixel is expressed by 8 bits) into 4-level output data (M=256 and N=4), will be described as a typical example of the multi-level error diffusion process.
The 4-level quantization output value after error diffusion is set to one of O1 (blank dot or vacancy), O2 (small dot), O3 (middle dot) and O4 (large dot). The gradation of each of the four quantization output values is set to 0, 85, 170 and 255, and the threshold is set to the middle of each output value; 43, 128 and 213, respectively. In the following, a case in which O1 (blank dot) is a white dot and O4 (255) is a black dot will be considered. However, the opposite case in which O1 is a black dot and O4 is a white dot may be considered instead.
In a case where a simple 4-level error diffusion process is performed for a 128-level gradation image, when the gradation of the input value is less than 85, the gradation is expressed by O1 (blank dot) and O2 (small dot). When the gradation of the input value is equal to 85, it is expressed by filling O2 (small dot). When the gradation of the input value is larger than 86, the gradation is expressed by O2 (small dot) and O3 (middle dot).
FIG. 3 shows the result of a simple 4-level error diffusion process which is performed for each pixel of a 128-level gradation image. In the case of FIG. 3, the gradation value of the input image changes from 0 to 128. As shown in the FIG. 3, depending on the ratio and the processing direction of changing the gradation, the generation of the output dots O3 (middle dot) is delayed in the gradation value 86, and the portion with the output dots O2 (small dot) will be spread.
Similarly, in a case of another 128-level gradation image in which the gradation value of the image changes from 128 to 0, the same phenomenon takes place when the error diffusion process is performed. The generation of the output dots O1 (blank dot) is delayed in the gradation value 84, and the portion filled with the output dots O2 (small dot) will be spread.
The gradation representation is expressed by filling the output dots O1 (blank dot), O2 (small dot), O3 (middle dot) and O4 (large dot), respectively, when the gradation values of the input are 0, 85, 170 and 255 in the above example (or when the quantization output value and the input value of the N-level error diffusion are the same). It is not mixed with other output values in the portion, and the frequency characteristic of the image becomes uniform and the graininess is good.
On the other hand, in other portions, the gradation representation is expressed by a combination of the N-level quantization output values and the two output values coexist in these portions, and the frequency characteristic of the image will be confused. That is, in the gradation image in which the input gradation value changes from 0 to 128, only the portion with the gradation value 85 will have good graininess and other portions with different gradation values will have poor graininess, and therefore the sense of incongruity arises.
When the gradation value of the input image changes from 0 to 128, the graininess in the vicinity of the portion with the gradation value 85 will be changed in a pattern of the disordered image, the uniform image and the disordered image. The uniform image interposed between the disordered images becomes visible.
Thus, the gradation level difference or the pseudo outline arises in the changing portion (for example, the gradation value 85, the gradation value 170) where the quantization output value changes.
On the other hand, the graininess in the vicinity of the portion with the gradation value 0 will be changed in a pattern of the uniform image and the disordered image, and it becomes invisible.
In the portions near the white background portion (the gradation value 0) or the solidly shaded portion (the gradation value 255), the sense of incongruity will not arise due to the human visual prejudice.
In the neighboring portion (the gradation value 1) of the portion with the gradation value 0, the delay of the dot generation for the gradation value 1 in the error diffusion process, which cause the area of the white background to increase, will be the problem, and the sense of incongruity of the graininess will not be the problem.
As mentioned above, the portions with the gradation values 85 and 86 of FIG. 3 are filled with the output dots O2 (small dot). The portion with the gradation value 86 is originally reproduced with a combination of many output dots O2 (small dot) and some output dots O3 (middle dot). However, in the image of FIG. 3, the output dots O3 (middle dot) are not outputted.
Thus, the delay of the dot generation in the changing portions of the 4-level quantization output causes the gradation-level difference (pseudo outline) to arise in the changing portion (the gradation value 85), and the quality of image will deteriorate. The same problem exists in the changing portion (the gradation value 170).
As a conventional technology directed to overcoming the delay of the dot generation, Japanese Laid-Open Patent Application No. 7-111591 discloses an image processing device. In this image processing device, the threshold is varied according to concentration, in order to eliminate the delay of output dot generation in the highlight portion and the delay of blank dot generation in the solidly shaded portion for the 2-level error diffusion process.
Moreover, Japanese Laid-Open Patent Application No. 10-257302 discloses an image processing device which is directed to overcoming the delay of the dot generation for the multiple-level error diffusion process and raising the sharpness.
The conventional techniques of the above-mentioned documents have solved the problem of image distortion by the delay of the dot generation. However, in the conventional techniques no consideration is given to eliminate the problem of the deterioration of picture quality due to the delay of the dot generation in the changing portions where the N-level quantization output value by the multi-level error diffusion process changes.
A conceivable method to eliminate the above problem is that a certain noise is added to the changing portion where the quantization output value changes, and the middle dots and the blank dots are made to appear there so that the level difference (pseudo outline) will not be conspicuous. FIG. 4 shows the result of adding a random number with the amplitude ±32 to the gradation value 85 when the error diffusion process is performed.
However, according to such method, the middle dots appear in the gradation value 85 more frequently than in the gradation values 86 and 87, and the gradation will be reversed.
Moreover, since the random number is added, the occurrence positions of the blank dots and the middle dots are in disorder, and the graininess may be poor. The use of the random number is not suitable for high-speed processing.